package com.jason.algorithm;

public class AlgorithmHard {

    /**
     * 获取最大的黄金重量  采用动态规划算法
     * @param golds  金矿
     * @param personNum  总人数
     * @return
     */
    public static int getMaxWeight(Gold [] golds, int personNum) {
        if (golds == null || personNum <= 0) {
            //没有金矿，没有人挖掘
            return 0;
        }
        //每个金矿的重量和需要的人数
        int [] weights = new int[golds.length];
        int [] persons = new int[golds.length];
        for (int i = 0; i < golds.length; i++) {
            weights[i] = golds[i].getWeight();
            persons[i] = golds[i].getPerson();
        }

        //dp方程  循环每一座金矿
        int [][] value = new int [golds.length + 1][personNum + 1];
        for (int i = 1; i <= golds.length; i ++) {
            //每座金矿派去的人数
            for (int j = 1; j <= personNum; j ++) {
                if (j < persons[i - 1]) {
                    //如果人数少于当前金矿需要的人数  不挖该金矿  价值是上一轮的价值
                    value[i][j] = value[i -1][j];
                } else {
                    //挖该金矿  最大价值 = 当前金矿的价值 + 上一金矿是的最大价值
                    value[i][j] = Math.max(value[i -1][j], weights[i - 1] + value[i - 1][j - persons[i -1]]);
                }
            }
        }

        String choice = "选中金矿编号：";
        int j = personNum;
        for (int i = golds.length; i > 0; i --) {
            if (value[i][j] > value[i-1][j]) {
                //该金矿选中
                choice = choice + i + " ";
                //剩下的人数
                j = j - persons[i - 1];
            }
            if (j == 0) {
                //没人了 没有金矿可以选择了
                break;
            }
        }
        System.out.println(choice);

        return value[golds.length][personNum];
    }

    /**
     * 测试
     * @param args
     */
    public static void main(String[] args) {
        Gold gold1 = new Gold(500, 5);
        Gold gold2 = new Gold(300, 4);
        Gold gold3 = new Gold(200, 2);
        Gold gold4 = new Gold(600, 7);
        Gold gold5 = new Gold(400, 5);
        Gold [] golds = {gold1, gold2, gold3, gold5, gold4};
        System.out.println(getMaxWeight(golds, 10));
    }


}
